Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks
Scaffold：基于支撑图理论的图神经网络稀疏化框架
🧭 图神经网络稀疏化 · 支撑图理论
Pacific Northwest National Laboratory · University of Texas at Dallas · University of North Carolina at Charlotte · Adobe · Boise State University
用支撑图理论联合控制 dilation 与 congestion 的拓扑稀疏化方法，在 GNN 上大幅降存提速且保持性能
📌 工作参考价值（4 点）
- 在大规模 user-item 二部图或商品知识图谱上训练 GNN 时，可将 Scaffold 作为预处理边稀疏化步骤，替代随机采样或度中心性采样，在 10%-50% 边保留率下接近全图性能，显存占用减半以上，适合电商推荐中的大规模图训练。
- dilation-congestion 联合约束可以直接借鉴到构建轻量图子图或缓存图结构：删边时评估替代路径长度（dilation）和路径集中度（congestion），避免切断关键通信路径，对实时推荐或增量更新子图有工程价值。
- 方法在异配图（heterophilic）上同样有效，可用于处理社交关系、用户共现等噪声连接较多的场景，提升 GNN 抗噪能力。
- 已开源实现，作为独立预处理模块可快速接入 PyG/DGL 训练流程，端到端训练时间（含稀疏化开销）仍低于全图训练，适合线上迭代。